//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
using namespace std;

class Solution {
private:
    vector<vector<string>> res;
    string s;
public:
    //方法一：回溯
    void dfs1(int startIndex, vector<string> &path){
        if (startIndex==s.length()){
            res.push_back(path);
            return;
        }

        for (int i = startIndex; i < s.length(); ++i) {
            if (!checkPalindrome(s, startIndex, i))continue;
            path.push_back(s.substr(startIndex, i-startIndex+1));
            dfs1(i+1, path);
            path.pop_back();
        }
    }
    vector<vector<string>> partition1(string s) {
        this->s = s;
        vector<string> path;
        dfs1(0, path);
        return res;
    }

    bool checkPalindrome(string str, int left, int right){
        while (left<right){
            if (str[left]!=str[right])return false;
            left++;
            right--;
        }
        return true;
    }

    //方法二 动态规划
    vector<vector<string>> partition(string s) {
        if(s.length()==0)return res;
        int n = s.length();
        //定义状态数组
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        //初始化， 对角线为true
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }
        //状态转移,先控制列
        for (int j = 1; j < n ; j++) {//列
            for (int i = 0; i < j; i++) {//行, 不等于
                //【i，j】
                bool  isCharEqual = s[i]==s[j];
                if(j-i==1){
                    dp[i][j] = isCharEqual;
                }else if(!isCharEqual){
                    dp[i][j] = false;
                }else{
                    dp[i][j] = dp[i+1][j-1];
                }
            }
        }
        vector<string> path;
        dfs(0, path, dp);
        return res;
    }

    void dfs(int startIndex, vector<string>& path, vector<vector<bool>> dp){
        if (startIndex == s.length()) {
            res.emplace_back(path);
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (!dp[startIndex][i]) continue;
            path.push_back(s.substr(startIndex, i - startIndex + 1));
            dfs(i + 1, path, dp);
            path.pop_back();
        }
    }

};